package MonotonicStack;

import java.util.Stack;

/**
 * 84. 柱状图中最大的矩形
 * 困难
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */
public class largestRectangleArea {
    //一刷二刷思路一样
    /**
     * 单调栈
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int[] h = new int[heights.length + 2];
        h[0] = 0;
        h[h.length - 1] = 0;
        for (int i = 1; i < h.length - 1; i++) {
            h[i] = heights[i - 1];
        }
        int max = 0;
        stack.push(0);
        for (int i = 1; i < h.length; i++) {
            if (h[i] > h[stack.peek()]) {
                stack.push(i);
            } else if (h[i] == h[stack.peek()]) {
                stack.pop();    // 这个可以加，可以不加，效果一样，思路不同
                stack.push(i);
            } else {
                while (!stack.isEmpty() && h[stack.peek()] > h[i]) {
                    int middle = stack.peek();
                    stack.pop();
                    if (!stack.isEmpty()) {
                        int w = i - stack.peek() - 1;
                        int height = h[middle];
                        max = Math.max(max, height * w);
                    }
                }
                stack.push(i);
            }
        }
        return max;
    }
    public int largestRectangleArea1(int[] heights) {
        int[] newHeight = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeight, 1, heights.length);
        newHeight[heights.length + 1] = 0;
        newHeight[0] = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int res = 0;
        for (int i = 1; i < newHeight.length; i++) {
            while (newHeight[i] < newHeight[stack.peek()]) {
                int mid = stack.pop();
                int w = i - stack.peek() - 1;
                int h = newHeight[mid];
                res = Math.max(res, w * h);
            }
            stack.push(i);
        }
        return res;
    }


}
